区间dp

一.概念

对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。

二.基本思路

阅读全文 »

伯努利数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下:

i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1} i B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

CF113D Museum

fi,jf_{i,j}:两人分别在房间 i,ji,j 的概率。初始状态 fa,b=1f_{a,b}=1

fi,j=pipjfi,j+(i,u)E(j,v)E1pudegu1pvdegvfu,vf_{i,j}=p_ip_jf_{i,j}+\sum_{(i,u) \in E}\sum_{(j,v) \in E} \frac{1-p_u}{\deg_u} \frac{1-p_v}{\deg_v}f_{u,v}

阅读全文 »